package lc.q5400_q5450;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 句子」是一个用空格分隔单词的字符串。给你一个满足下述格式的句子 text :
 *
 * 句子的首字母大写
 * text 中的每个单词都用单个空格分隔。
 * 请你重新排列 text 中的单词，使所有单词按其长度的升序排列。如果两个单词的长度相同，则保留其在原句子中的相对顺序。
 *
 * 请同样按上述格式返回新的句子。
 *
 */
public class Q5413 {

    public static class StringAndOrder {
        private String word;
        private int order;

        public StringAndOrder(String word, int order) {
            this.word = word;
            this.order = order;
        }

        public String getWord() {
            return word;
        }

    }

    public String arrangeWords2(String text) {
        // 优先级队列不稳定，要保证稳定型，可以对比较算法增加内容，比如把序号也放进去

        final PriorityQueue<StringAndOrder> strings = new PriorityQueue<>((o1, o2) -> {
            if (o1.word.length() == o2.word.length()) {
                return o1.order - o2.order;
            } else {
                return o1.word.length() - o2.word.length();
            }
        });
        final String[] s = text.split(" ");
        if (s.length < 1) {
            return text;
        }
        for (int i = 0; i < s.length; i++) {
            strings.add(new StringAndOrder(s[i],i));
        }
        String join = strings.stream().map(StringAndOrder::getWord).collect(Collectors.joining(" "));
        join = join.substring(0,1).toUpperCase() + (join.length() > 1?join.substring(1):"");
        return join;
    }

    public String arrangeWords(String text) {
        if (text.length() == 0) {
            return text;
        }
        // 寻找一种稳定算法
        final String s = text.toLowerCase();
        final String[] words = s.split(" ");
        if (words.length <= 1) {
            return text;
        }
        // 构建一个SortedMap
        final TreeMap<Integer, LinkedList<String>> map = new TreeMap<>();
        for (String word : words) {
            map.putIfAbsent(word.length(), new LinkedList<>());
            final LinkedList<String> list = map.get(word.length());
            list.add(word);
        }
        int i = 0;
        for (Map.Entry<Integer, LinkedList<String>> entry : map.entrySet()) {
            final LinkedList<String> value = entry.getValue();
            for (String s1 : value) {
                words[i] = s1;
                i ++;
            }
        }
        // 将word[0]的首字母大小
        words[0] = words[0].substring(0,1).toUpperCase() + (words[0].length()>1?words[0].substring(1):"");
        return String.join(" ",words);
    }

    public static void main(String[] args) {
        final Q5413 q5413 = new Q5413();
        final String keep_calm_and_code_on = q5413.arrangeWords2("Keep calm and code on");
        System.out.println(keep_calm_and_code_on);
    }

}
